//最小路径和
/*给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。*/
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> ret(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int n1, n2;
                // int n1 = i - 1 >= 0 ? ret[i - 1][j] : 0;
                // int n2 = j - 1 >= 0 ? ret[i][j - 1] : 0;
                // ret[i][j] = grid[i][j] + min(n1, n2);
                if (i - 1 < 0 || j - 1 < 0) {
                    if (i - 1 >= 0) {
                        n1 = ret[i - 1][j];
                        ret[i][j] = grid[i][j] + n1;

                    } else if (j - 1 >= 0) {
                        n2 = ret[i][j - 1];
                        ret[i][j] = grid[i][j] + n2;
                    } else {
                        ret[i][j] = grid[i][j];
                    }
                } else {
                    n1 = ret[i - 1][j];
                    n2 = ret[i][j - 1];
                    ret[i][j] = grid[i][j] + min(n1, n2);
                }
            }
        }
        return ret[m - 1][n - 1];
    }
};

//寻找峰值
/*峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。*/
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1, m;
        while (l < r) {
            m = l + (r - l) / 2;
            if (nums[m] > nums[m + 1])
                r = m;
            else
                l = m + 1;
        }
        return l;
    }
};